package com.arron.algorithm.leetcodetop100.动态规划.背包问题;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.Arrays;


public class 零钱兑换 {


    int[] amounts;


    /**
     *  coins = [1,2,5] amount = 11,选出用最少的硬币数量凑齐11
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {

        if (amount <0){
            return 0;
        }

        //带记忆的递归
        amounts = new int[amount+1];

        Arrays.fill(amounts,amount+1);
        amounts[0]  = 0;
        return coinsChose(coins,amount);

    }

    public int coinsChose(int[] coins, int amount){

        if (amount<0){
            return -1;
        }
        if (amount ==0) return 0;

        if (amounts[amount] != amounts.length) {
            return amounts[amount];
        }
        int res =Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {

            int  sub = coinsChose(coins, amount - coins[i]);

            if (sub <0){
                continue;
            }
            res = Math.min(res,sub+1);
        }
        amounts[amount] = res == Integer.MAX_VALUE?-1:res;
        return amounts[amount];
    }



}
